#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        /*
        vector<int> ans;
        int left=0;
        int right=nums.size()-1;
        int mid=0;
        int left_tmp=left;
        int right_tmp=right;
        while(left<=right){
            mid=(left+right)/2;
            if(nums[mid]<target){
                left=mid+1;
                left_tmp=left;
            } else if(nums[mid]>target){
                right=mid-1;
                right_tmp=right;
            } else{
                left_tmp=(left+mid)/2;
                //cout<<"left:"<<left<<",left_tmp:"<<left_tmp<<endl;
                while(true){
                    if(nums[left]==target){
                        //cout<<"left:"<<left<<",left_tmp:"<<left_tmp<<endl;
                        break;
                    } else if(nums[left]<target&&nums[left_tmp]<target){
                        left=left_tmp+1;
                        left_tmp=(left+left_tmp+1)/2;
                    } else{
                        left_tmp=(left+left_tmp)/2;
                    }
                    //cout<<"left:"<<left<<",left_tmp:"<<left_tmp<<endl;
                }

                right_tmp=(right+mid)/2;
                //cout<<"right:"<<right<<",right_tmp:"<<right_tmp<<endl;
                while(true){
                    if(nums[right]==target){
                        //cout<<"right:"<<right<<",right_tmp:"<<right_tmp<<endl;
                        break;
                    } else if(nums[right]>target&&nums[right_tmp]>target){
                        right=right_tmp-1;
                        right_tmp=(right+mid)/2;
                    } else{
                        right_tmp=(right_tmp+right+1)/2;
                    }
                    //cout<<"right:"<<right<<",right_tmp:"<<right_tmp<<endl;
                }

                if(nums[left]==target&&nums[right_tmp]==target){
                    //cout<<"left:"<<left<<",left_tmp"<<left_tmp<<",mid:"<<mid<<",right:"<<right<<",right_tmp:"<<right_tmp<<endl;

                    ans.push_back(left);
                    ans.push_back(right);
                    return ans;
                }
                
            }
            //cout<<"left:"<<left<<",left_tmp:"<<left_tmp<<",mid:"<<mid<<",right:"<<right<<",right_tmp:"<<right_tmp<<endl;
        }
        ans.push_back(-1);
        ans.push_back(-1);
        return ans;
        */
        vector<int> ans(2,-1);
        int len=nums.size();
        int l=0;
        int r=len-1;
        int mid=0;
        while(l<r){
            mid=(l+r)/2;
            if(nums[mid]>=target){  
                r=mid;
            } else{
                l=mid+1;
            }
            cout<<"l-- "<<"l:"<<l<<",r:"<<r<<endl;
        }
        if(nums[l]!=target){
            return ans;
        }
        ans[0]=l;
        cout<<"left complete!"<<endl;
        r=len;
        while(l<r){
            mid=(l+r)/2;
            if(nums[mid]<=target){
                l=mid+1;
            } else{
                r=mid;
            }
            cout<<"r-- "<<"l:"<<l<<",r:"<<r<<endl;
        }
        ans[1]=l-1;
        return ans;
    }
};

int main(){
    Solution s;
    //vector<int> in{0,0,1,2,3,3,4};
    //vector<int> in{1,1,2,2,5,5,6,7,8,8,9};
    //vector<int> in{5,7,7,8,8,10};
    vector<int> in{1,1,1,1};
    //vector<int> in{2,2,2,2};
    for(int i=0;i<in.size();i++){
        cout<<in[i]<<" ";
    }
    cout<<endl;

    vector<int> out; 
    int target=1;
    out=s.searchRange(in,target);
    for (size_t i = 0; i < out.size(); i++)
    {
        cout<<out[i]<<" ";
    }
    cout<<endl;
}

/*
//利用二分思想先找其左边界，再找其右边界即可，注意找左边界的时候，由右侧逼近；找右边界的时候，由左侧逼近，即可。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> res(2,-1);
        if(nums.empty()) return res;
        int n=nums.size(),l=0,r=n-1;
        while(l<r){
            int m=l+(r-l)/2;
            if(nums[m]>=target) r=m;
            else l=m+1;
        }
        if(nums[l]!=target) return res;
        res[0]=l;
        r=n;
        while(l<r){
            int m=l+(r-l)/2;
            if(nums[m]<=target) l=m+1;
            else r=m;
        }
        res[1]=l-1;
        return res;
    }
};
*/
/*
5 7 8 8 9 10 11 12 12

1 8 8 8 8 8 8 9  

2 2 2 2 2 2 2 2


*/

//两个二分查找
/*
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {

        vector<int> res(2,-1);
        if(nums.empty()){
            return res;
        }
        if(nums.size()==1){
            if(nums[0]==target){
                res[0]=0;
                res[1]=0;
            }
            return res;
        }

        int left=0;
        int right=nums.size();
        int mid=0;
        while(left<right){
            mid=left+(right-left)/2;
            if(nums[mid]==target){
                right=mid;
            }else if(nums[mid]<target){
                left=mid+1;
            }else if(nums[mid]>target){
                right=mid;
            }
            cout<<"l:"<<left<<" r:"<<right<<" mid:"<<mid<<endl;
        }

        if(left<nums.size()&&nums[left]==target){
            res[0]=left;
        }
        cout<<"over"<<endl;
        left=0;
        right=nums.size();
        mid=0;
        while(left<right){
            mid=left+(right-left)/2;
            if(nums[mid]==target){
                left=mid+1;
            }else if(nums[mid]<target){
                left=mid+1;
            }else if(nums[mid]>target){
                right=mid;
            }
            cout<<"l:"<<left<<" r:"<<right<<" mid:"<<mid<<endl;
        }
        if(left-1<nums.size()&&nums[left-1]==target){
            res[1]=left-1;
        }
        return res;

    }
};
*/